Bit maps offer a compact method of storing data describing the allocation state of memory pages in computing systems. The location of pages which are un-allocated may be determined algorithmically from the location of bits of a predetermined state. The condition of bit maps may be characterized by the density and distribution of bits of the state indicating the existence of an un-allocated page. It is a property of bit map search methods that some may be efficient when the map is sparsely populated with un-allocated pages while others may be efficient when the map is densely populated.
There are a number of articles and issued patents directed to memory search features, each having certain advantages and disadvantages.
IBM TDB, Vol. 22, No. 6, November 1979, pp 2489-90, entitled "Parallel Table Directed Translation" describes a method for performing vector operations such as a search process which uses p processors simultaneously and which is based solely on comparisons of search arguments on parallel processors of a single instruction multiple data stream (SIMD) type. The parallel computer implementable method searches multiple similar or dissimilar search arguments over the same table in order to obtain multiple outcomes. More particularly, the method is directed to the concurrent translation of p search arguments over the same linked list of vectors, which vectors form a preordered binary search tree on p processors. This requires each processor independently comparing a search argument with an ordered recursive scanning of a copy of the search tree. If there is a match, then a concordance between the search argument and a translation value is indicated. For a mismatch, a left or right tree search is executed if the search argument is respectively less than or greater than the nodal value.
U.S. Pat. No. 4,482,956, entitled, "Parallel Queueing Method" is directed to enabling a single chained queue to have parallel operations by plural element insertion routines and one deletion routine which may be simultaneously executing asynchronously on plural processors for deleting an element, while inserting one or more anchor-pointed elements. This is done by providing a dequeueing lock which is only examined by a program routine which is to delete an element, but is not examined by any program routine which is to make an insertion of an anchor-pointed element into the queue using a System/370 compare and swap instruction.
U.S. Pat. No. 4,639,856 entitled, "Dual Stream Processor Apparatus" sets forth a duel stream processor apparatus, for use in a multiprocessor computer system. The multiprocessor computer system includes at least a first processor and a second processor. A first apparatus and a second apparatus is included in both the first processor and the second processor for use when either the first or the second processor is inoperative. The first apparatus, disposed within the inoperative processor, suspends the functional operation of the inoperative processor. The second apparatus, disposed within the inoperative processor, transmits a miss signal to the other remaining functionally operational processor. When the other remaining processor receives the miss signal, it will not subsequently attempt to locate desired data in the cache of the inoperative processor. Rather, the other remaining processor will search for the desired data in the main memory in the event it cannot locate the data in its own cache.
According to the subject invention, a bit map search mechanism is implemented which supports parallel search of the bit map by differently optimized search methods so that the map search is optimized across the range of conditions. A bit map search is set forth in which a pair of dedicated microprocessors, each implementing a differently optimized search procedure, compete to be first to find a bit indicating an un-allocated page. On finding such a bit the successful microprocessor interrupts the losing processor. The losing processor is given the bit location and is responsible for updating the bit map and summary buffers while the winning processor calculates the free page location and informs the larger system.